import java.util.Arrays;

public class lianXuZiShuZuZuiDaHe {
    /**
     * 连续子数组的最大和
     * 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。
     */
    /*
    采用动态规划,定义一个dp 数组,其中dp[i]表示以第i个元素结尾的最大数组和.对于dp[i]:
    1.如果dp[i-1] + array[i] < array[i],那么dp[i]就等于array[i],表示以array[i]为起点重新计算最大子数组和
    2.如果dp[i-1] + array[i] >= array[i],表示当前元素可以加入之前的最大数组和
    在计算dp[i]的同时,记录最大数组和的起点和终点,以便返回最大子数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        int n = array.length;
        int[] dp = new int[n];
        dp[0] = array[0];
        int max = dp[0],start = 0,end = 1,temp = 0;
        for (int i = 1; i < n; i++) {
            if (dp[i-1] + array[i] < array[i]) {
                dp[i] = array[i];
                temp = i;
            }else {
                dp[i] = dp[i-1] + array[i];
            }
            if (dp[i] >= max) {
                max = dp[i];
                start = temp;
                end = i + 1;
            }
        }
        return Arrays.copyOfRange(array,start,end);
    }
}
